//给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 
//
// 
//
// 示例： 
//
// 输入：
//A: [1,2,3,2,1]
//B: [3,2,1,4,7]
//输出：3
//解释：
//长度最长的公共子数组是 [3, 2, 1] 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= len(A), len(B) <= 1000 
// 0 <= A[i], B[i] < 100 
// 
// Related Topics 数组 二分查找 动态规划 滑动窗口 哈希函数 滚动哈希 👍 598 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Random;

public class MaximumLengthOfRepeatedSubarray {
    public static void main(String[] args) {

        int[] nums1 = {0,0,0,0,0,0,1,0,0,0};
        int[] nums2 = {0,0,0,0,0,0,0,1,0,0};
        new MaximumLengthOfRepeatedSubarray().new Solution().findLength(nums1,nums2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 看了题解才知道怎么用dp去解
         * dp[i][j]表示当前A数组取到[i-1] B数组取到[j-1]时的最大长度
         * 如果两个数组数字相等，就直接取上一个位置的值+1 dp[i][j] = dp[i-1][j-1]+1
         * 可以压缩到一维dp，注意第二个维度要从后向前遍历，且不相等是赋值为0
         */
        public int findLength(int[] nums1, int[] nums2) {
            int res = 0;
            int[] dp = new int[nums2.length+1];
            for (int i = 1; i <= nums1.length; i++) {
                for (int j = nums2.length; j > 0 ; j--) {//逆序遍历压缩到一维
                    if (nums1[i-1] == nums2[j-1]) dp[j] = dp[j-1] + 1;
                    else dp[j] = 0;//压缩到一维之后需要赋值为0才行
                    if (dp[j] > res) res = dp[j];
                }
            }
            return res;
        }

        /**
         * 题解中的另一个解法：滑动窗口法，两数组相对滑动，只比较重合的部分是否一样
         */
        public int findLength2(int[] nums1, int[] nums2) {
            return nums1.length < nums2.length ? findMax(nums1, nums2) : findMax(nums2, nums1);
        }

        /**
         * 这里传入的两个数组第一个一定是小数组
         * 即A的长度小于B的长度
         * 模拟的是A在上B在下滑动的过程
         */
        public int findMax(int[] A, int[] B){
            int max = 0;
            int aLen = A.length;
            int bLen = B.length;
            //滑动过程分为三部分：进入过程（重叠长度增加），完全重叠过程（重叠长度不变），滑出过程（重叠长度变小）
            //滑入过程
            for (int len = 1; len <= aLen ; len++) {
                max = Math.max(max,maxLen(A,0,B,bLen - len, len));
            }
            //完全重叠过程
            for (int i = bLen-aLen; i >= 0 ; i--) {
                max = Math.max(max,maxLen(A,0, B, i, aLen));
            }
            //滑出过程
            for (int i = 1; i <= aLen-1 ; i++) {
                max = Math.max(max,maxLen(A, i, B,0,aLen-i));
            }
            return max;
        }

        /**
         *
         * @param i 短数组起始下标
         * @param j 长数组起始下标
         * @param len 重叠长度
         * @return 最大重叠长度
         */
        public int maxLen(int[] a, int i, int[] b, int j, int len) {
            int count = 0, max = 0;
            for (int k = 0; k < len; k++) {
                if (a[i+k] == b[j+k]) count++;
                else if (count > 0) {
                    max = Math.max(max,count);
                    count=0;
                }
            }
            return Math.max(count,max);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}